package com.example.demo.shuatiban.zuocheng;

import java.util.HashMap;

/**
 * @author xujm
 * @version V2.4
 * 给定一个数组arr 可以在每个数字之前+ 或者 - ，但是所有的数字必须参与，
 * 再给定一个数字target 请问最后算出target的方法数是多少
 * @since 2.4.0 2022/1/31 12:40
 */
public class Arr_数字加减求出最后值 {




    public static int process2(int i, int [] arr, int rest){

        if(i == arr.length){
            if(rest == 0){
                return 1;
            }
            return 0;
        }

        int count = 0;
        int j = i+1;
        count= count + process2(j,arr,rest+arr[i]);
        count = count + process2(j,arr,rest-arr[i]);
        return count;
    }

    /**
     * 记忆化搜索
     */
    public static int process3(int i,int [] arr, int rest, HashMap<Integer,HashMap<Integer,Integer>> dp){
        if(dp.containsKey(i) && dp.get(i).containsKey(rest)){
            return dp.get(i).get(rest);
        }
        if(i == arr.length){
            if(rest == 0){
                return 1;
            }
            return 0;
        }
        int count = 0;
        count= count + process2(i+1 ,arr,rest+arr[i]);
        count = count + process2(i+1 ,arr,rest-arr[i]);
        // i,new HashMap<>(rest,count)
        if(dp.containsKey(i)){
            HashMap<Integer, Integer> temp = dp.get(i);
            temp.put(rest,count);
        }else{
            HashMap<Integer, Integer> temp = new HashMap<>();
            temp.put(rest,count);
            dp.put(i,temp);
        }
        return count;

    }
    /**
     * 动态规划
     *  观察记忆化搜索的解法 process3，
     *  (1)其中i和rest是两个变量，设置dp[][]数组 以i,rest为下标，填充结果数
     *  (2)当i==arr.length,rest == 0 时，结果数为1, 当i == arr.length, rest !=0 时，结果数为0
     *
     *      假设三个数是  1,1,1  那么最大rest不会超过3,
     *     可以得到 rest  0   1   2   3
     *               i
     *               0    0   1   0   0
     *               1
     *               2
     *               3    1   0   0   0

     *      第2行的值，通过观察记忆化搜索可以知道是通过第三行得出的:
     *      dp[i][rest] = dp[i+1][rest+arr[i]] + dp[i+1][rest-arr[i]];
     *
     * 通过上面的公式继续推导rest  0   1   2   3
     *      *                 i
     *      *                 0    0   2   0   1
     *      *                 1    1   0   1   0
     *      *                 2    0   1   0   0
     *      *                 3    1   0   0   0
     *      为什么差一个?????
     *
     * @param arr
     * @return
     */
    public static int process4(int [] arr, int target){
        int sum = 0;
        for(int temp : arr){
            sum+=temp;
        }
        int [][] dp = new int[arr.length+1][sum+1];
        HashMap<Integer,HashMap<Integer,Integer>> map = new HashMap<>();
        HashMap<Integer,Integer> val =new HashMap<>();
        val.put(0,1);
        map.put(arr.length,val);
        dp[arr.length][0] = 1;
        for(int i=dp.length-2;i>=0;i--){
            for(int rest=-sum;rest<dp[0].length;rest++){
                    if(map.get(i) == null){
                        HashMap temp = new HashMap<Integer, Integer>();
                        Integer a = map.get(i+1).get(rest+arr[i]);
                        Integer b =map.get(i+1).get(rest-arr[i]);
                        a = a != null? a:0;
                        b = b != null? b:0;
                        a = a > 0 ? a : 0;
                        b = b > 0 ? b : 0;
                        temp.put(rest, a+b);
                        map.put(i,temp);
                    }else{
                        HashMap<Integer, Integer> mmap = map.get(i);
                        Integer a = map.get(i+1).get(rest+arr[i]);
                        Integer b =map.get(i+1).get(rest-arr[i]);
                        a = a != null? a:0;
                        b = b != null? b:0;
                        a = a > 0 ? a : 0;
                        b = b > 0 ? b : 0;
                        if(mmap.get(rest) != null){
                            mmap.put(rest, a+b+mmap.get(rest));
                        }else{
                            mmap.put(rest, a+b);
                        }
                        map.put(i,mmap);
                        // map.get(i).get(rest) = map.get(i+1).get(rest+arr[i]) + map.get(i+1).get(rest-arr[i]);
                    }
            }
        }
        return map.get(0).get(target);
    }


    public static int process(int i, int [] arr,int result, int target){

        if(i >= arr.length){
            if(result == target){
                return 1;
            }
            return 0;
        }

        int count = 0;
        int j = i+1;
        count= count + process(j,arr,result+arr[i],target);
        count = count + process(j,arr,result-arr[i],target);
        return count;
    }

    public static int process5(int[] arr, int target) {
        int base = 0;
        for (int v : arr) {
            base += Math.abs(v);
        }
        int total = 2 * base;
        int[][] dp = new int[arr.length + 1][total + 1];
        dp[1][base + arr[0]] = dp[1][base - arr[0]] = 1;
        for (int i = 2; i <= arr.length; i++) {
            for (int j = 0; j <= total; j++) {
                int v = dp[i - 1][j];
                if (v > 0) {
                    dp[i][j + arr[i - 1]] += v;
                    dp[i][j - arr[i - 1]] += v;
                }
            }
        }

        return dp[arr.length][target + base];
    }
    public static void main(String[] args) {
         int [] arr = {1,1,1};
        HashMap<Integer,HashMap<Integer,Integer>> map = new HashMap<>();
        System.out.println(process(0,arr,0,1));
        System.out.println(process2(0,arr,1));
        System.out.println(process3(0,arr,1,map));

        //动态规划解法 还差一个. 必须考虑 rest有可能是负数的情况!!!!
        System.out.println(process4(arr,1));
        System.out.println(process5(arr,1));

        // int [] arr2={1,2,3,2,2,3,3};
        // for(int i=0;i<100;i++){
        //     int a = process2(0,arr2,i);
        //     int b = process4(arr2,i);
        //     System.out.print( "a:"+a+" b:"+b+" ");
        //     System.out.println(a==b);
        // }
    }


}
